package com.lw.leetcode.hash.c;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * hash
 * 2045. 到达目的地的第二短时间
 *
 * @author liw
 * @version 1.0
 * @date 2022/2/8 11:36
 */
public class SecondMinimum {

    public static void main(String[] args) {
        SecondMinimum test = new SecondMinimum();

        // 输出：13
        int n = 5;
        int[][] arr = {{1, 2}, {1, 3}, {1, 4}, {3, 4}, {4, 5}};
        int time = 3;
        int change = 5;

        // 11
//        int n = 2;
//        int[][] arr = {{1, 2}};
//        int time = 3;
//        int change = 2;


        // 12
//        int n = 6;
//        int[][] arr ={{1,2},{1,3},{2,4},{3,5},{5,4}, {4, 6}};
//        int time = 3;
//        int change = 100;

        int i = test.secondMinimum(n, arr, time, change);
        System.out.println(i);
    }

    private Map<Integer, Set<Integer>> map = new HashMap<>();
    private int n;
    private int count;
    private int[] arr;
    private int flag = 0;

    public int secondMinimum(int n, int[][] edges, int time, int change) {
        this.n = n;
        this.arr = new int[n + 1];
        Arrays.fill(arr, 2);
        for (int[] edge : edges) {
            int a = edge[0];
            int b = edge[1];
            map.computeIfAbsent(a, v -> new HashSet<>()).add(b);
            map.computeIfAbsent(b, v -> new HashSet<>()).add(a);
        }
        Set<Integer> a = new HashSet<>();
        Set<Integer> b = new HashSet<>();
        a.add(1);
        find(a, b, 0);
        if (flag == 1) {
            count += 2;
        }
        return find(count, time, change);
    }

    private void find(Set<Integer> a, Set<Integer> b, int index) {
        if (a.isEmpty() || (count != 0 && index > count + 1)) {
            return;
        }
        for (int v : a) {
            if (v == n) {
                count = index;
                flag++;
                if (flag == 2) {
                    return;
                }
            }
            for (int next : map.get(v)) {
                if (b.contains(next)) {
                    continue;
                }
                if (arr[next] > 0) {
                    arr[next]--;
                    b.add(next);
                }
            }
        }
        a.clear();
        find(b, a, index + 1);
    }

    private int find(int count, int time, int change) {
        int sum = 0;
        for (int i = 0; i < count; i++) {
            int t = sum / change;
            if ((t & 1) == 0) {
                sum += time;
            } else {
                sum = (t + 1) * change + time;
            }
        }
        return sum;
    }

}
